package chapter02;

import java.util.HashMap;

public class MinWindow76 {
    /**
     * 滑动窗口
     * L=0 R=0 [L,R) R表明是右边界且不包含
     * 哈希表记录t中每个字符需要数  count记录需要的总字符数
     * 1).count>0 扩大窗口
     *    a).s[R]在hash表中个数>0 说明窗口没有包含完s[R]字符
     *      count--
     *    b).否则
     *      表明 该窗口内s[R]字符已经满足数量 无需修改count
     *    无论哪种情况都需要扩大窗口 右边界移动将s[R]包含进去 哈希表s[R]个数-1  R++
     * 2).否则 缩短窗口
     *    a).如果count==0
     *      说明还需要0个字符 窗口内已包含t全部字符
     *      更新最小字串
     *    无论哪种情况 尝试缩短窗口
     *    如果s[L]在哈希值中值>=0 表明窗口去掉s[L]后 窗口内还需要s[L]字符 count++
     *    缩短窗口 哈希表s[L]个数+1 让左边界右移L++
     */
    public String minWindow(String s, String t) {
        char[] chs=s.toCharArray();
        char[] cht=t.toCharArray();
        HashMap<Character,Integer> charMap=new HashMap<>();
        int count=0;
        for(int i=0;i<cht.length;i++){
            charMap.put(cht[i],charMap.getOrDefault(cht[i],0)+1);
            count++;
        }
        int left=0,right=0,start=0,end=0,min=Integer.MAX_VALUE;
        while (left<=right){
            if(count>0){
                if(right==chs.length){
                    break;
                }
                char c=chs[right++];
                if(charMap.containsKey(c)){
                    if(charMap.get(c)>0){
                        count--;
                    }
                    charMap.put(c,charMap.get(c)-1);
                }
            }else{
                if(count==0&&right-left<min){
                    start=left;
                    end=right;
                    min=right-left;
                }
                char c=chs[left++];
                if(charMap.containsKey(c)){
                    if(charMap.get(c)>=0){
                        count++;
                    }
                    charMap.put(c,charMap.get(c)+1);
                }
            }
        }
        return s.substring(start,end);
    }
}
